package slidingwindow.leetcode_3;

import java.util.HashSet;

public class SlidingWindow {
    /*
        使用散列表HashSet
     */
    public int lengthOfLongestSubstring(String s) {
        // 记录无重复子串的最大长度
        int maxLen = 0;
        // 滑动窗口的左右边界
        int left = 0;
        int right = 0;
        HashSet<Character> set = new HashSet<>();
        while (right < s.length()) {
            // 如果当前遍历到的字符已经在窗口中，说明重复，将重复元素及其前面的字符全部删除
            while (set.contains(s.charAt(right))) {
                /*
                    这里可以优化的点，当发现了一个已经存在的字符，窗口的左边界移动到重复字符的下一个字符开始即可，而不需要遍历删除
                    比如：abcbad
                        当遍历到第 2 个 b 时，左边界直接设置到字符 c 所在下标即可。
                 */
                set.remove(s.charAt(left++));
            }
            // 添加到窗口中
            set.add(s.charAt(right++));
            // 记录最大长度
            maxLen = Math.max(maxLen, set.size());
        }
        return maxLen;
    }
    /*
        使用队列
    public int lengthOfLongestSubstring(String s) {
        Deque<Character> deque = new LinkedList<>();
        int res = 0;
        for (char c : s.toCharArray()){
            //如果队列中存在该字符，就弹出队头元素，直至不存在该字符
            while(deque.contains(c)){
                deque.poll();
            }
            deque.add(c);
            res = Math.max(res, deque.size());
        }
        return res;
    }
     */
}
